package Basic_DataStructures.BinarySearch;

public class BinarySearch {

    /**
     * 二分查找
     * @param array  有序的升序数组
     * @param target 查找的目标元素
     * @return       目标元素在数组中的索引
     */
    public static int binarySearch(int[] array, int target){
        //初始位置
        int start = 0;//前指针
        int end = array.length - 1;//后指针

        //范围内还存在元素
        while (start <= end){//确保当start=end时，还会进行一次判断
            //中间索引
            int middle = (start + end)/2;
            if(array[middle] < target){//目标处于中值右侧
                start = middle + 1;
            }else if(array[middle] > target){//目标处于中值左侧
                end = middle -1;
            }else {
                return middle;
            }
        }

        return -1;//未找到返回-1
    }
}
